package com.sourcetrip.algorithm.sort.heap;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;
import com.sourcetrip.utils.printer.BinaryTreeInfo;

/**
 * @author: ZhouBert
 * @date: 2020/12/29
 * @description:	十大排序算法之三：堆排序（的对象比较版本）
 */
public class HeapCustomedSortV0<E> extends AbstractCustomedObjectSort<E> implements BinaryTreeInfo {

	private int heapSize = 0;

	@Override
	protected void sortArr(E[] objectArr) {
		heapSize = objectArr.length;
		elements = objectArr;

		//BinaryTrees.println(this);
		//1.原地建堆
		heapify(objectArr);

		//2.迭代（依然使用冒泡排序的模板）
		//2.1.

		int size = objectArr.length;
		for (int end = objectArr.length - 1; end >= 0; end--) {
			swap(0, end);
			siftDown(0, objectArr, --size);
		}
	}

	//region	core methods

	private void heapify(E[] arr) {
		int size = arr.length;
		for (int i = getParentIndex(arr.length - 1); i >= 0; i--) {
			siftDown(i, arr, size);
			//BinaryTrees.println(this);
		}
	}

	/**
	 * 将 index 处的元素下滤（考虑数组中大小为 size）
	 *
	 * @param index
	 * @param size
	 */
	private void siftDown(int index, E[] arr, int size) {
		int rightIndex = getRightIndex(index);
		int biggerIndex = 0;
		while (rightIndex < size) {
			//存在 左节点
			if (compare(arr[rightIndex - 1], arr[rightIndex]) < 0) {
				//右边大于左边 -> 等于时使用左边，在这一步保证稳定
				biggerIndex = rightIndex;
			} else {
				biggerIndex = rightIndex - 1;
			}
			if (compare(arr[index], arr[biggerIndex]) < 0) {
				swap(index, biggerIndex);

				index = biggerIndex;
				rightIndex = getRightIndex(index);
			} else {
				break;
			}
		}
		//如果只有一个左子节点
		if (rightIndex == size) {
			//比较左子节点和 index
			if (compare(arr[index], arr[rightIndex - 1]) < 0) {
				swap(index, rightIndex - 1);
			}
		}

	}

	/**
	 * 通过 index 拿到 parent index
	 *
	 * @param index
	 * @return
	 */
	private int getParentIndex(int index) {
		return (index - 1) >> 1;
	}

	/**
	 * 获取 index 的右节点索引
	 *
	 * @param index
	 * @return
	 */
	private int getRightIndex(int index) {
		return (index << 1) + 2;
	}


	//endregion

	/**
	 * 找到节点的右节点
	 *
	 * @param node
	 * @return
	 */
	@Override
	public Object right(Object node) {
		int index = ((int) node << 1) + 2;
		return index >= heapSize ? null : index;
	}

	@Override
	public Object root() {
		return 0;
	}

	@Override
	public Object left(Object node) {
		int index = ((int) node << 1) + 1;
		return index >= heapSize ? null : index;
	}

	@Override
	public Object string(Object node) {
		return elements[(int) node];
	}
}
